package 面试v1.字节;

import leetcodev1.链表.Solution;

import java.util.ArrayList;
import java.util.List;

public class LeetCode679 {

    boolean ret = false;

    //先选2个数进行加减乘除 在和剩余两个数进行递归操作
    public boolean judgePoint24(int[] cards) {
        int length = cards.length;
        boolean[] visited = new boolean[length];
        dfs(cards, visited, 0, 0);
        return ret;
    }

    //回溯
    private void dfs(int[] cards, boolean[] visited, int sum, int visitedCount) {
        if (ret) {
            return;
        }

        if (visitedCount == 4) {
            if (sum == 24) {
                ret = true;
            }
            return;
        }

        int length = visited.length;
        for (int i = 0; i < length; i++) {
            if (visited[i]) {
                continue;
            }

            visited[i] = true;
            dfs(cards, visited, sum + cards[i], visitedCount++);
            dfs(cards, visited, sum - cards[i], visitedCount++);
            if (visitedCount == 0) {
                sum = 1;
            }
            dfs(cards, visited, sum * cards[i], visitedCount++);
            dfs(cards, visited, sum / cards[i], visitedCount++);
            visited[i] = false;
        }
    }
}

class Answer679 {
    static final int TARGET = 24;
    static final double EPSILON = 1e-6;
    static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;

    public boolean judgePoint24(int[] nums) {
        List<Double> list = new ArrayList<Double>();
        for (int num : nums) {
            list.add((double) num);
        }
        return solve(list);
    }

    public boolean solve(List<Double> list) {
        if (list.size() == 0) {
            return false;
        }
        if (list.size() == 1) {
            return Math.abs(list.get(0) - TARGET) < EPSILON;
        }
        int size = list.size();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i != j) {
                    List<Double> list2 = new ArrayList<Double>();
                    for (int k = 0; k < size; k++) {
                        if (k != i && k != j) {
                            list2.add(list.get(k));//非i j元素 继续递归的集合
                        }
                    }
                    //遍历4种操作
                    for (int k = 0; k < 4; k++) {
                        if (k < 2 && i > j) {
                            //加和乘可以忽略顺序
                            continue;
                        }
                        if (k == ADD) {
                            list2.add(list.get(i) + list.get(j));
                        } else if (k == MULTIPLY) {
                            list2.add(list.get(i) * list.get(j));
                        } else if (k == SUBTRACT) {
                            list2.add(list.get(i) - list.get(j));
                        } else if (k == DIVIDE) {
                            if (Math.abs(list.get(j)) < EPSILON) {
                                continue;
                            } else {
                                list2.add(list.get(i) / list.get(j));
                            }
                        }
                        if (solve(list2)) {
                            return true;
                        }
                        list2.remove(list2.size() - 1);//执行回溯，将中间结果删除掉
                    }
                }
            }
        }
        return false;
    }
}
